/**
  @(#)$Id: AL_QueuePriorityCircularSeq.h 73 2013-10-10 12:38:11Z xiaoting $
  @brief   
  ////////////////////////////////Priority queue (priority queue)e//////////////////////////////////////////
  Common queue is a FIFO data structure, the end of an additional element in the queue, and the head removed from the queue. In the 
  priority queue element is given priority. When accessing the element, the element with the highest priority first removed. Priority 
  queue with the highest first-out (largest-in, first-out) the behavioral characteristics.

  Priority queue is 0 or more elements of the collection, each element has a priority or value of the operations performed on the 
  priority queue with a) Find; 2) Insert a new element; 3) Delete in the minimum priority queue (min priorityq ueue), the lookup 
  operation to search for smallest element priority, delete operation to remove the element; for maximum priority queue (max priority 
  queue), lookup to search for the largest element of the priority, delete operation is used remove the element. priority queue 
  element can have the same priority, find and delete operations can be carried out according to any priority.\
  
  To take advantage of vector space, to overcome the "false overflow" phenomenon is: the vector space imagined as an end to 
  end of the ring, saying such a vector is cyclic vector. Stored in a queue which is called circular queue (Circular Queue).
  
  A queue is a special linear form, so special is that it only allows the front end of the table (front) delete operation, 
  and the rear end of the table (rear) for insertion, and the stack, as the queue is an operating by restricted linear form. Insert 
  operation is called the tail end, the end delete operation called HOL. No element in the queue, it is called an empty queue.
  
  This data structure in the queue, the first element inserted will be the first element to be removed; otherwise the last inserted 
  element will be the last element to be removed, so the queue is also known as "first in first out" (FIFO-first in first out) linear 
  form.

  ////////////////////////////////Sequential storage structure//////////////////////////////////////////
  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 
  the linear order of the table storage structure.

  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 
  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 
  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 
  language (e.g., c / c) of the array to describe.

  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 
  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 
  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 
  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 
  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
          
  Benefits:
	Random Access table elements. 
  Disadvantages: 
    insert and delete operations need to move elements.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:38:11 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 73 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueuePriorityCircularSeq.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueuePriorityCircularSeq.h 73 2013-10-10 12:38:11Z xiaoting $
 */

#ifndef CXX_AL_QUEUEPRIORITYCIRCULARSEQ_H
#define CXX_AL_QUEUEPRIORITYCIRCULARSEQ_H

#ifndef CXX_AL_FUNCTIUONAL_H
#include "AL_Functional.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_QueuePriorityCircularSeq
///////////////////////////////////////////////////////////////////////////

template<typename T, typename Compare = al_less<T> > 
class AL_QueuePriorityCircularSeq
{
public:
	static const DWORD QUEUESEQ_DEFAULTSIZE			= 100;
	static const DWORD QUEUESEQ_MAXSIZE				= 0xffffffff;
	/**
	* Construction Constructed using the default priority queue
	*
	* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
	* @return
	* @note
	* @attention	The default precedence relations: big > small
	*/
	AL_QueuePriorityCircularSeq(DWORD dwSize = QUEUESEQ_DEFAULTSIZE);

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_QueuePriorityCircularSeq();

	/**
	* IsEmpty
	*
	* @param	VOID
	* @return	BOOL
	* @note		Returns true queue is empty
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Front
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the first element at the front of the queue.
	* @attention
	*/
	BOOL Front(T& tTypeOut) const;

	/**
	* Back
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the last and most recently added element at the back of the queue.
	* @attention
	*/
	BOOL Back(T& tTypeOut) const;

	/**
	* Pop
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Removes an element from the front of the queue.
	* @attention
	*/
	BOOL Pop(T& tTypeOut);

		
	/**
	* Push
	*
	* @param	VOID
	* @return	DWORD
	* @note		Adds an element to the back of the queue.
	* @attention	
	*/
	VOID Push(const T& tData);

	/**
	* Size
	*
	* @param	VOID
	* @return	DWORD
	* @note		Returns the number of elements in the queue
	* @attention
	*/
	DWORD Size() const;

	/**
	* Clear
	*
	* @param	VOID
	* @return	VOID
	* @note		clear all data
	* @attention
	*/
	VOID Clear();
	
protected:
private:
	/**
	* GetBuffer
	*
	* @param VOID
	* @return VOID
	* @note get the work buffer
	* @attention when the buffer is not enough, it will become to double
	*/
	VOID GetBuffer();
	
	/**
	* IsFull
	*
	* @param VOID
	* @return BOOL
	* @note the buffer is full?
	* @attention
	*/
	BOOL IsFull() const;

	/**
	*Copy Construct
	*
	* @param const AL_QueuePriorityCircularSeq<T, Compare>& cAL_QueuePriorityCircularSeq
	* @return
	*/
	AL_QueuePriorityCircularSeq(const AL_QueuePriorityCircularSeq<T, Compare>& cAL_QueuePriorityCircularSeq);

	/**
	*Assignment
	*
	* @param const AL_QueuePriorityCircularSeq<T, Compare>& cAL_QueuePriorityCircularSeq
	* @return AL_QueuePriorityCircularSeq<T, Compare>&
	*/
	AL_QueuePriorityCircularSeq<T, Compare>& operator = (const AL_QueuePriorityCircularSeq<T, Compare>& cAL_QueuePriorityCircularSeq);

public:
protected:
private: 
	T*			m_pElements;
	DWORD		m_dwMaxSize;
	DWORD		m_dwSize;

	DWORD		m_dwFront;
	DWORD		m_dwRear;
};


/**
* Construction Constructed using the default priority queue
*
* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
* @return
* @note
* @attention	The default precedence relations: big > small
*/
template<typename T, typename Compare> 
AL_QueuePriorityCircularSeq<T, Compare>::AL_QueuePriorityCircularSeq(DWORD dwSize):
m_pElements(NULL),
m_dwMaxSize(dwSize),
m_dwSize(0x00),
m_dwFront(0x00),
m_dwRear(0x00)
{
	if (0x00 == m_dwMaxSize) {
		//for memory deal
		m_dwMaxSize = 1;
	}
	GetBuffer();
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T, typename Compare> 
AL_QueuePriorityCircularSeq<T, Compare>::~AL_QueuePriorityCircularSeq()
{
	if (NULL != m_pElements) {
		delete[] m_pElements;
		m_pElements = NULL;
	}
}

/**
* IsEmpty
*
* @param	VOID
* @return	BOOL
* @note		Returns true queue is empty
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityCircularSeq<T, Compare>::IsEmpty() const
{
	return (0x00 == m_dwSize) ? TRUE:FALSE;
}


/**
* Front
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the first element at the front of the queue.
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityCircularSeq<T, Compare>::Front(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pElements[m_dwFront];
	return TRUE;
}

/**
* Back
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the last and most recently added element at the back of the queue.
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityCircularSeq<T, Compare>::Back(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pElements[m_dwRear];
	return TRUE;
}

/**
* Pop
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Removes an element from the front of the queue.
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityCircularSeq<T, Compare>::Pop(T& tTypeOut)
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}
	tTypeOut = m_pElements[m_dwFront];
	//memset(&m_pElements[m_dwFront], 0x00, sizeof(T));		//can not use memset, as to pointer or virtural pointer of class
	
	m_dwFront = (m_dwFront+1)%m_dwMaxSize;
	
	m_dwSize--;
	return TRUE;
}

	
/**
* Push
*
* @param	VOID
* @return	DWORD
* @note		Adds an element to the back of the queue.
* @attention	
*/
template<typename T, typename Compare> VOID 
AL_QueuePriorityCircularSeq<T, Compare>::Push(const T& tData)
{
	if (TRUE == IsFull()) {
		// full, need to get more work buffer
		GetBuffer();
	}

	if (0x00 == m_dwFront && TRUE == IsEmpty()) {
		//the first time Push, not need to ++
		m_dwRear = 0x00;
		m_pElements[m_dwRear] = tData;
	}
	else {
		m_dwRear = (m_dwRear+1)%m_dwMaxSize;

		DWORD dwPos=m_dwSize;
		for (; dwPos>0; dwPos--) {
			//loop all elements: from the back
			if (FALSE == Compare()(tData, m_pElements[(m_dwFront+dwPos-1)%m_dwMaxSize])) {
				break;
			}

		}
		
		if ((dwPos+m_dwFront)%m_dwMaxSize == m_dwRear) {
			//smallest in the queue
			m_pElements[m_dwRear] = tData;
		}
		else {
			for (DWORD dwCount=0x00; dwCount<m_dwSize-dwPos; dwCount++) {
				//m_dwSize = m_dwRear - m_dwFront + 1
				if (dwCount+1 <= m_dwRear) {
					m_pElements[m_dwRear-dwCount] = m_pElements[m_dwRear-dwCount-1];
				}
				else {
					if (dwCount <= m_dwRear) {
						m_pElements[m_dwRear-dwCount] = m_pElements[m_dwRear+m_dwMaxSize-dwCount-1];
					}
					else {
						m_pElements[m_dwRear+m_dwMaxSize-dwCount] = m_pElements[m_dwRear+m_dwMaxSize-dwCount-1];
					}
					
				}
			}
			m_pElements[(m_dwFront+dwPos)%m_dwMaxSize] =  tData;
		}
	}
	
	m_dwSize++;
}

/**
* Size
*
* @param	VOID
* @return	DWORD
* @note		Returns the number of elements in the queue
* @attention
*/
template<typename T, typename Compare> DWORD 
AL_QueuePriorityCircularSeq<T, Compare>::Size() const
{
	return m_dwSize;
}

/**
* Clear
*
* @param	VOID
* @return	VOID
* @note		clear all data
* @attention
*/
template<typename T, typename Compare> VOID 
AL_QueuePriorityCircularSeq<T, Compare>::Clear()
{
	//memset(m_pElements, 0x00, sizeof(T)*Size());		//can not use memset, as to pointer or virtural pointer of class
	m_dwSize = 0x00;
	m_dwFront = 0x00;
	m_dwRear = 0x00;
}


/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
template<typename T, typename Compare> VOID 
AL_QueuePriorityCircularSeq<T, Compare>::GetBuffer()
{

	if ( (FALSE == IsFull()) && (NULL != m_pElements) ) {
		//we do not need to get more buffer
		return;
	}

	if (NULL == m_pElements) {
		if(0 < m_dwMaxSize){
			//get the new work buffer
			m_pElements = new T[m_dwMaxSize];
			//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
		}
		return;
	}

	//we need to get more buffer, store the previous pointer
	T* pLastTpye = NULL;

	// it will become to double
	pLastTpye = m_pElements;
	if (QUEUESEQ_MAXSIZE == m_dwMaxSize) {
		//can not get more buffer, please check the application
		return;
	}
	else if (QUEUESEQ_MAXSIZE/2 < m_dwMaxSize) {
		m_dwMaxSize = QUEUESEQ_MAXSIZE;
	}
	else {
		m_dwMaxSize *= 2;
	}
	if(0 < m_dwMaxSize){
		//get the new work buffer
		m_pElements = new T[m_dwMaxSize];
		//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
	}
	//need to copy the last to the current, not Contiguous memory
	for (DWORD dwCpy=0x00; dwCpy<Size(); dwCpy++) {
		m_pElements[dwCpy] = pLastTpye[(m_dwFront+dwCpy)%Size()];
	}
					
	for (DWORD dwCpy2=0x00; dwCpy2<m_dwFront; dwCpy2++) {
		m_pElements[Size()-m_dwFront+dwCpy2] = pLastTpye[dwCpy2];
	}
	//memcpy(m_pElements, &pLastTpye[m_dwFront], sizeof(T)*(Size()-m_dwFront));	//can not use memcopy, as to pointer
	//memcpy(m_pElements+(Size()-m_dwFront), &pLastTpye[0], sizeof(T)*m_dwFront);	//can not use memcopy, as to pointer
	
	//m_dwFront move to the front
	m_dwFront = 0x00;
	//m_dwFront move to the rear
	m_dwRear = Size() - 1;

	//free the last work buffer
	delete[] pLastTpye;
	pLastTpye = NULL;
}

/**
* IsFull
*
* @param
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityCircularSeq<T, Compare>::IsFull() const
{
	return (m_dwMaxSize <= Size()) ? TRUE:FALSE;

// 	/*"Sacrifice a unit", ie rear +1 = front (accurately recorded is (rear +1)% m = front, m is the queue capacity) 
// 	when the team is full.*/
// 	if (TRUE == IsEmpty()) {
// 		return FALSE;
// 	}
// 
// 	return ((m_dwRear+1)%m_dwMaxSize == m_dwFront) ? TRUE:FALSE;
}

#endif // CXX_AL_QUEUEPRIORITYCIRCULARSEQ_H
/* EOF */
